#ifndef MKAHYPAR_SEARCH_INITIAL_PARTITIONER_H
#define MKAHYPAR_SEARCH_INITIAL_PARTITIONER_H

#include <queue>
#include "mkahypar/partition/initial_partitioning/i_initial_partitioner.h"
#include "mkahypar/partition/initial_partitioning/initial_partitioner_base.h"

//基于搜索的初始划分
//先放大节点，然后再一圈圈地扩展
namespace mkahypar {
  class SearchInitialPartitioner : public IInitialPartitioner,
                                   private InitialPartitionerBase<SearchInitialPartitioner> {
    using Base = InitialPartitionerBase<SearchInitialPartitioner>;
  public:
    SearchInitialPartitioner(Hypergraph &hypergraph, TargetGraph &targetGraph) :
            Base(hypergraph, _topo) {
    }

    ~SearchInitialPartitioner() override = default;

    //初始划分
    void initialPartition() {
      //识别关键顶点
      std::vector<std::pair<double, HypernodeID>> cirtical_nodes;
      cirtical_nodes.reserve(_hg._num_hypernodes);
      for (auto v: _hg.nodes()) {
        cirtical_nodes.emplace_back(getMaxResPercent(v),v);
      }
      std::sort(cirtical_nodes.begin(),cirtical_nodes.end(),[](auto &a,auto&b){
        return a.first > b.first;
      });
      //认为前10%的顶点需要优先放置
      int threshold = 0.1 * cirtical_nodes.size();
      threshold = std::max(1,threshold);//至少确保有1个
      std::queue<HypernodeID>que;
      for(int i=0;i<threshold;++i)
        que.emplace(cirtical_nodes[i].second);

      //开始扩展放置
      while(!que.empty()){

      }



    }

    //计算节点最大的资源的占比
    double getMaxResPercent(HypernodeID v) {
      auto &fpga_res = _topo._fpga[0]._bound_res;
      double p = 0;
      for (int i = 0; i < _hg.hypernode(v).weight().size(); ++i) {
        if (_hg.hypernode(v).weight()[i] != 0) {
          double x = static_cast<double>(_hg.hypernode(v).weight()[i]) /
                     static_cast<double>(fpga_res[i]);
          p = std::max(p, x);
        }
      }
      return p;
    }


  private:
    //核心划分算法
    void partitionImpl() {

    }


  };
}
#endif //MKAHYPAR_SEARCH_INITIAL_PARTITIONER_H
